#include <queue>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
// 思路： 使用队列进行层序遍历，同时比较每一层的节点是否对称
//   具体做法是每次从队列中取出两个节点进行比较，如果两个节点都为空则继续比较下一个节点
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        if (!root)
            return true;
        queue<pair<TreeNode *, TreeNode *>> q; // 左子树和右子树节点对
        q.push({root->left, root->right});     // 初始化队列
        while (!q.empty())                     // 使用队列进行层序遍历
        {
            auto [left, right] = q.front(); // 取出队列中的节点对
            q.pop();                        // 弹出队列中的节点对
            if (!left && !right)            // 两个节点都为空，继续比较下一个节点
                continue;
            if (!left || !right) // 只有一个节点为空，说明不对称
                return false;
            if (left->val != right->val) // 节点值不相等，说明不对称
                return false;
            q.push({left->left, right->right}); // 将左子节点和右子节点入队
            q.push({left->right, right->left}); // 将右子节点和左子节点入队
        }
        return true;
    }
};